package com.sali.数据结构;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
 */
public class LeetCode_402 {


    public String removeKdigits(String num, int k) {
        if ( num.length() == k ) {
            return "0";
        }
        Deque<Character> myStack = new ArrayDeque<>();

        int index = 0;

        while ( index < num.length() ) {
            while ( k > 0 && !myStack.isEmpty() && myStack.peek() > num.charAt(index) )  {
                k--;
                myStack.pop();
            }
            myStack.push(num.charAt(index));
            index++;
        }

        while ( k > 0 ) {
            myStack.pop();
            k--;
        }

        StringBuilder sb = new StringBuilder();
        while ( !myStack.isEmpty() ) {
            sb.append(myStack.pop());
        }
        StringBuilder sb2 = new StringBuilder();
        String tmp = sb.reverse().toString();
        boolean found = false;
        for ( int i = 0; i < tmp.length(); i++  ) {
            if ( tmp.charAt(i) != '0'  ) {
                found = true;
                sb2.append(tmp.charAt(i));
            } else if ( found ) {
                sb2.append(tmp.charAt(i));
            }
        }
        if ( sb2.length() == 0 ) {
            return "0";
        }
        return sb2.toString();
    }
}
